#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
简化的Elliptic Curve数学库
用于Power仿True的小模数Elliptic Curve实现

Support的曲线：
- Tiny Curve (64-bit)
- secp128r1 (128-bit)
- secp160r1 (160-bit)

优点：
1. 小模数便于快速Calculate
2. True实的Elliptic Curve点运算
3. 保持侧信道泄漏特性
"""

import random
from typing import Tuple, Optional


class SimplifiedECCPoint:
    """简化的Elliptic Curve点"""
    
    def __init__(self, x: Optional[int], y: Optional[int], curve: 'SimplifiedECCCurve'):
        """
        InitializeElliptic Curve点
        
        Args:
            x: x坐标（None表示No穷远点）
            y: y坐标
            curve: 所属曲线
        """
        self.x = x
        self.y = y
        self.curve = curve
        self.is_infinity = (x is None)
    
    def __repr__(self):
        if self.is_infinity:
            return "Point(∞)"
        return f"Point({hex(self.x)[:16]}, {hex(self.y)[:16]})"
    
    def double(self) -> 'SimplifiedECCPoint':
        """点倍乘：2P"""
        if self.is_infinity:
            return self
        
        curve = self.curve
        
        # Calculate斜率 λ = (3x² + a) / (2y) mod p
        numerator = (3 * self.x * self.x + curve.a) % curve.p
        denominator = (2 * self.y) % curve.p
        denominator_inv = pow(denominator, curve.p - 2, curve.p)  # 费马小定理
        lambda_val = (numerator * denominator_inv) % curve.p
        
        # Calculate新点坐标
        x3 = (lambda_val * lambda_val - 2 * self.x) % curve.p
        y3 = (lambda_val * (self.x - x3) - self.y) % curve.p
        
        return SimplifiedECCPoint(x3, y3, curve)
    
    def add(self, other: 'SimplifiedECCPoint') -> 'SimplifiedECCPoint':
        """点加法：P + Q"""
        if self.curve != other.curve:
            raise ValueError("Points must be on the same curve")
        
        # No穷远点Process
        if self.is_infinity:
            return other
        if other.is_infinity:
            return self
        
        # 相同点的加法就Yes倍乘
        if self.x == other.x and self.y == other.y:
            return self.double()
        
        # 互For逆元的点相加得No穷远点
        if self.x == other.x:
            return SimplifiedECCPoint(None, None, self.curve)
        
        curve = self.curve
        
        # Calculate斜率 λ = (y2 - y1) / (x2 - x1) mod p
        numerator = (other.y - self.y) % curve.p
        denominator = (other.x - self.x) % curve.p
        denominator_inv = pow(denominator, curve.p - 2, curve.p)
        lambda_val = (numerator * denominator_inv) % curve.p
        
        # Calculate新点坐标
        x3 = (lambda_val * lambda_val - self.x - other.x) % curve.p
        y3 = (lambda_val * (self.x - x3) - self.y) % curve.p
        
        return SimplifiedECCPoint(x3, y3, curve)
    
    def scalar_multiply(self, k: int) -> 'SimplifiedECCPoint':
        """
        Scalar乘法：k*P (Double-and-AddAlgorithm)
        
        这YesECC中最关键的操作，也YesSide-Channel Attack的主要目标
        """
        if k == 0 or self.is_infinity:
            return SimplifiedECCPoint(None, None, self.curve)
        
        if k < 0:
            raise ValueError("Scalar must be non-negative")
        
        # Double-and-AddAlgorithm
        result = SimplifiedECCPoint(None, None, self.curve)  # No穷远点
        addend = self
        
        while k:
            if k & 1:  # IfCurrent位Yes1，Execute点加法
                result = result.add(addend)
            addend = addend.double()  # 每次都Execute点倍乘
            k >>= 1
        
        return result
    
    def get_x_bytes(self, byte_length: int = 16) -> bytes:
        """获取x坐标的字节表示"""
        if self.is_infinity:
            return b'\x00' * byte_length
        return self.x.to_bytes(byte_length, 'big')
    
    def get_y_bytes(self, byte_length: int = 16) -> bytes:
        """获取y坐标的字节表示"""
        if self.is_infinity:
            return b'\x00' * byte_length
        return self.y.to_bytes(byte_length, 'big')


class SimplifiedECCCurve:
    """简化的Elliptic Curve"""
    
    def __init__(self, name: str, p: int, a: int, b: int, gx: int, gy: int, n: int):
        """
        InitializeElliptic CurveParameters
        
        Args:
            name: 曲线名称
            p: Has限域模数
            a, b: 曲线方程 y² = x³ + ax + b
            gx, gy: 基点G的坐标
            n: 基点的阶
        """
        self.name = name
        self.p = p
        self.a = a
        self.b = b
        self.gx = gx
        self.gy = gy
        self.n = n
        self.G = SimplifiedECCPoint(gx, gy, self)
        self.bit_length = p.bit_length()
        self.byte_length = (self.bit_length + 7) // 8
    
    def __repr__(self):
        return f"Curve({self.name}, {self.bit_length}-bit)"
    
    def is_on_curve(self, point: SimplifiedECCPoint) -> bool:
        """Verify点YesNoIn曲线上"""
        if point.is_infinity:
            return True
        
        # Verify y² = x³ + ax + b (mod p)
        left = (point.y * point.y) % self.p
        right = (point.x ** 3 + self.a * point.x + self.b) % self.p
        return left == right
    
    def random_private_key(self) -> int:
        """Generate随机私钥"""
        return random.randint(1, self.n - 1)
    
    def generate_keypair(self) -> Tuple[int, SimplifiedECCPoint]:
        """GenerateKey对"""
        private_key = self.random_private_key()
        public_key = self.G.scalar_multiply(private_key)
        return private_key, public_key


# 预定义的小曲线Parameters

def get_tiny_curve() -> SimplifiedECCCurve:
    """
    超小曲线 (64-bit) - 仅用于Test
    这个曲线Not安全，但Calculate极快
    """
    # Use质数 p = 2^64 - 59
    p = 18446744073709551557
    a = 0
    b = 7
    # 简化的基点（NotYesTrue实的secp256k1基点，只Yes一个Test点）
    gx = 12345678901234567890
    gy = 9876543210987654321
    n = p  # 简化，实际应该Yes基点的阶
    
    return SimplifiedECCCurve("tiny64", p, a, b, gx, gy, n)


def get_secp128r1() -> SimplifiedECCCurve:
    """
    secp128r1 - NIST推荐的128位曲线
    适合Power仿True：Calculate快，但保持True实ECC特性
    """
    # secp128r1 Parameters（来自SECG标准）
    p = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF
    a = 0xFFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC
    b = 0xE87579C11079F43DD824993C2CEE5ED3
    gx = 0x161FF7528B899B2D0C28607CA52C5B86
    gy = 0xCF5AC8395BAFEB13C02DA292DDED7A83
    n = 0xFFFFFFFE0000000075A30D1B9038A115
    
    return SimplifiedECCCurve("secp128r1", p, a, b, gx, gy, n)


def get_secp160r1() -> SimplifiedECCCurve:
    """
    secp160r1 - 160位曲线
    平衡Calculate速度AndTrue实性
    """
    # secp160r1 Parameters
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC
    b = 0x1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45
    gx = 0x4A96B5688EF573284664698968C38BB913CBFC82
    gy = 0x23A628553168947D59DCC912042351377AC5FB32
    n = 0x0100000000000000000001F4C8F927AED3CA752257
    
    return SimplifiedECCCurve("secp160r1", p, a, b, gx, gy, n)


# 便捷Function

def get_curve(name: str = "secp128r1") -> SimplifiedECCCurve:
    """
    获取指定曲线
    
    Args:
        name: 曲线名称 ("tiny64", "secp128r1", "secp160r1")
    
    Returns:
        SimplifiedECCCurve对象
    """
    curves = {
        "tiny64": get_tiny_curve,
        "secp128r1": get_secp128r1,
        "secp160r1": get_secp160r1,
    }
    
    if name not in curves:
        raise ValueError(f"Unknown curve: {name}. Available: {list(curves.keys())}")
    
    return curves[name]()


# Test代码
if __name__ == "__main__":
    print("=" * 60)
    print("简化Elliptic Curve数学库Test")
    print("=" * 60)
    
    # Testsecp128r1
    curve = get_secp128r1()
    print(f"\n曲线: {curve}")
    print(f"模数位数: {curve.bit_length}")
    print(f"基点: {curve.G}")
    print(f"基点In曲线上: {curve.is_on_curve(curve.G)}")
    
    # TestScalar乘法
    print("\nTestScalar乘法:")
    k = 12345
    Q = curve.G.scalar_multiply(k)
    print(f"{k} * G = {Q}")
    print(f"ResultIn曲线上: {curve.is_on_curve(Q)}")
    
    # TestDouble-and-Add的每一步
    print("\nTestDouble-and-AddAlgorithm:")
    k = 5  # 二进制: 101
    print(f"k = {k} = 0b{bin(k)[2:]}")
    
    result = SimplifiedECCPoint(None, None, curve)
    addend = curve.G
    step = 0
    
    while k:
        print(f"\nStep {step}: k={k}, bit={k&1}")
        if k & 1:
            result = result.add(addend)
            print(f"  Execute点加法: result = result + addend")
        addend = addend.double()
        print(f"  Execute点倍乘: addend = 2 * addend")
        k >>= 1
        step += 1
    
    print(f"\nFinal result: {result}")
    print(f"Verify: {curve.is_on_curve(result)}")
    
    # 性能Test
    print("\n性能Test:")
    import time
    
    for curve_name in ["tiny64", "secp128r1", "secp160r1"]:
        curve = get_curve(curve_name)
        k = curve.random_private_key() % 1000  # 限制In1000以内加速Test
        
        start = time.time()
        Q = curve.G.scalar_multiply(k)
        elapsed = time.time() - start
        
        print(f"{curve_name:12s}: {k}*G 耗时 {elapsed*1000:.2f}ms")
